package algorithm.poj.p1000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 分析：
 * 无向完全图的最小生成树，这里用Kruskal算法
 * 
 * 实现：
 * 
 * 经验：
 * 
 * 教训：
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P1258 {

	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P1258.class.getResource("P1258.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		String line = stdin.readLine();
		while (line != null && !"0".equals(line)) {
			int N = Integer.valueOf(line);
			Vertex[] vs = new Vertex[N];
			for (int i = 0; i < N; i ++) {
				vs[i] = new Vertex(i);
			}
			Edge[] edges = new Edge[N*N];
			int index = 0;
			while (index < N*N) {
				line = stdin.readLine();
				StringTokenizer st = new StringTokenizer(line);
				while (st.hasMoreTokens()) {
					int i = index/N;
					int j = index%N;
					edges[index] = new Edge(i, j, Integer.valueOf(st.nextToken()));
					index ++;
				}
			}
			Arrays.sort(edges);
			int cost = 0;
			for (Edge edge: edges) {
				Vertex u = vs[edge.u];
				Vertex v = vs[edge.v];
				if (!UnionSearch.find(u).equals(UnionSearch.find(v))) {
					cost += edge.cost;
					UnionSearch.union(u, v);
				}
			}
			
			System.out.println(cost);
			line = stdin.readLine();
		}
	}
	
	private static class Vertex {
		
		private int index;
		private Vertex parent;
		private int rank;
		
		public Vertex(int index) {
			this.index = index;
			this.parent = this;
			this.rank = 0;
		}
		
		public boolean equals(Object o) {
			
			if (o == null || !(o instanceof Vertex)) {
				return false;
			} else {
				Vertex v = (Vertex)o;
				return v.index == this.index;
			}
		}
	}
	
	private static class Edge implements Comparable<Edge> {
		
		private int u;
		private int v;
		private int cost;

		public Edge(int u, int v, int cost) {
			this.u = u;
			this.v = v;
			this.cost = cost;
		}

		public int compareTo(Edge edge) {
			return Integer.valueOf(cost).compareTo(edge.cost);
		}
	}

	private static class UnionSearch {

		public static Vertex find(Vertex x) {
			
			if (x != x.parent) {
				x.parent = find(x.parent);
			}
			return x.parent;
		}
		
		public static void union(Vertex x, Vertex y) {
			
			link(find(x), find(y));
		}
		
		private static void link(Vertex x, Vertex y) {
			
			if (x.rank > y.rank) {
				y.parent = x;
			} else {
				x.parent = y;
				if (x.rank == y.rank) {
					y.rank ++;
				}
			}
		}
	}
}